Nel 1533 don Adamo Morfino, in seguito ad una promessa di voto, iniziò la costruzione di un ospedale per gli infermi e incurabili con annessa una cappella dedicata a San Paolo in Conversione, che a quei tempi si trovava alla fine dell'attuale Corso VI Aprile (allora chiamato "Corso Imperiale"). Tale costruzione, che era necessaria a causa dell'elevato numero di abitanti che richiedevano cure mediche, non arrivò ad essere ultimata completamente e venne chiusa nel 1590 per assenza di fondi.

 

A partire dal 1615, venne iniziata la costruzione della chiesa parrocchiale "San Paolo in Conversione" per volere dell'allora vescovo di Mazara, ampliando la precedente cappella di San Paolo in Conversione. Lo stesso vescovo fece costruire, contemporaneamente a quella di San Paolo in Conversione, la chiesa della Santissima Trinità che nel 1639 fu aggregata alla prima per rimediare alla mancanza di rendite.

 

Nel 1662 venne fondata la congregazione notturna di Santa Maria del Miele, alla quale partecipavano "uomini di campagna".

 

Nel 1689 la chiesa fu demolita e ricostruita grazie alle offerte dei fedeli, ultimando la costruzione nel 1692. Successivamente, essendo ancora disponibili offerte da parte dei fedeli (in particolare da parte del ricco possidente Mariano Balli), la chiesa fu ulteriormente ampliata (1702-1705), portando a termine la costruzione della cupola.

 

Nel 1765 venne fondata nella chiesa dei Santi Paolo e Bartolomeo la congregazione del Santissimo Viatico (successivamente chiamata congregazione del Sacro Cuore di Gesù), alla quale partecipavano "sacerdoti, gentiluomini, professori, benestanti e artigiani principali".

 

Tra il 1775 e il 1809 si procedette all'ultimazione del prospetto, alla costruzione delle cappelle laterali del Santissimo Sacramento in fondo e della Madonna dei Miracoli (patrona della città di Alcamo) e di un'antisagrestia. Durante questo periodo (precisamente nel 1778) fu inoltre collocato un orologio in rame nel campanile sulla facciata a sinistra (guardando dall'esterno), che fu sostituito nel 1846 con uno in acciaio e definitivamente rimosso nel 1910 in quanto non più funzionante. Nel 1916 fu poi restaurato l'altro dei campanili sulla facciata.

 

Dopo il terremoto del Belice del 1968, vennero svolte delle opere di restauro sulla facciata, eliminando la calce e lo stucco che erano stati aggiunti durante altre manutenzioni svolte in passato.

 

La chiesa, con pianta a croce latina, presenta tre navate, a ognuna della quali è associata una porta sul prospetto (una centrale e due laterali).

 

Sulla facciata, realizzata su disegno del 1782 di Emanuele Cardona, sono visibili due campanili, dove sono collocate 4 campane del peso complessivo di 20 quintali, delle quali una era utilizzata per il funzionamento dell'orologio non più esistente.

 

Le navate sono divise da due file di quattro colonne monolitiche di marmo rosso del monte Bonifato poggiate su basi di forma quadrangolare. L'abside presenta una finestra ad occhio, dove nel 1927 venne aggiunta una croce in ferro battuto.

 

Nella chiesa si trovano il battistero (decorato da Carlo Brunetti), entrando sul lato sinistro, e due altari sulle navate minori:

 

altare della Madonna dei Sette Angeli, a destra; Sette Arcangeli tela realizzata da Giuseppe Felice nel 1703;

altare di San Bartolomeo, a sinistra; tela dipinta da Narciso Guidone nel 1616.

Si trovano inoltre le seguenti cappelle:

 

cappella del Santissimo Crocifisso e cappella della Madonna del Miele sul transetto;

cappella del Santissimo Sacramento e cappella della Madonna di Pompei accanto al presbiterio.

Sull'abside si trova un dipinto su tela, raffigurante i Santi Paolo e Bartolomeo, realizzata da Giuseppe Felice nel 1701. Nella cappella della Madonna del Miele si trova un dipinto della Madonna del Miele risalente al 1300 circa, che è il più antico dipinto che si trova ad Alcamo. Tale dipinto proviene dalla chiesa di Santa Maria della Stella (che fu la prima chiesa madre di Alcamo) ed è attribuito a Barnaba da Modena.

 

La realizzazione degli stucchi all'interno della chiesa è dovuta a Vincenzo e Gabriele Messina, mentre gli affreschi sono opera di Antonio Grano.

 

Nella sacrestia della chiesa è conservata una tela del Sacro Cuore di Gesù, opera di Giuseppe Carta del 1858, e una statua del Sacro Cuore di Gesù, scolpita nel 1932 da Giuseppe Ospedale per conto della Congregazione che porta lo stesso nome: veniva portata in processione a fine luglio. Nell'antisagrestia c'è una tela di Giuseppe Carrera realizzata nel 1610 e che raffigura san Nicolò da Tolentino inginocchiato davanti a un altare e dentro una stanza buia, e il Simulacro ligneo della Madonna del Miele, scolpito nel 1846 dall'alcamese Giovanni Stellino. Veniva venerato sull'altare fino al 1903 ed è stato restaurato pochi anni fa da Rosa Maria Puma.